\section{Diameter-based objective}
\label{sec:theory2}
In this section, we mention theoretical results for {\it Diameter-sTF} and {\it Diameter-mTF}. We show that these problems are NP-hard (note that the NP-hardness of {\it Diameter-sTF} does not follow from any previous work). We further present an algorithm {\it MinDiameter} (Algorithm ~\ref{algo:minDia})  which is an extension of {\it RarestFirst} in~\cite{LLT}, and prove that it achieves a 2-approximation factor.
%Note that the NP-hardness of {\it Diameter-sTF} does not follow from any previous work. However, due to space constraints the proofs are omitted in this draft.

\begin{algorithm}[]\label{algo:minDia}
\caption{MinDiameter(G, {\cal T})} 
\label{algo:minDia}
\begin{algorithmic}[1]
\FOR{each $<a, k> \in T$}
\STATE $S(a) = \{ i \mid a \in X_i \}$
\ENDFOR
\STATE $a_{rare} = \arg \min_{<a, k>\ \in T} |S(a)|$
\FOR{each $i \in S(a_{rare})$}
\FOR{each $<a, k>\ \in T$}
\STATE $R_{ia} = d_k(i, S(a), k)$
\ENDFOR
\STATE $R_i \leftarrow \max_a R_{ia}$
\ENDFOR
\STATE $i^* \leftarrow \arg \min R_i$
\STATE ${\cal X'} = \{ i^* \}$
\FOR{each $<a, k>\ \in T$}
\STATE ${\cal X'} = {\cal X'} \cup \{  Path_k(i^*, S(a), k) \}$
\ENDFOR
\end{algorithmic}
\end{algorithm}

\begin{theorem} 
{\it Diameter-sTF} and {\it Diameter-mTF} problems are NP-complete.
\end{theorem}
\begin{proof}
The problems {\it Diameter-sTF} and {\it Diameter-mTF} are in NP because for a given candidate solution, in polynomial time, it can be verified that the skill-set requirement is satisfied. We prove that {\it Diameter-sTF} is NP-hard by reduction from the 3-satisfiability problem.  Consider a 3-SAT instance, say $\Psi = C_1 \wedge C_2 ... \wedge C_m$, where each clause, $C_j = (x \vee y \vee z)$, and $\lbrace x, y, z \rbrace \in U = \lbrace u_1, \neg u_1, u_2, \neg u_2, \cdot \cdot \cdot, u_n, \neg u_n \rbrace$. Let, $C = \lbrace  C_1, C_2, \cdot \cdot \cdot, C_m \rbrace$. Let $N, M$ denote the number of variables and clauses, respectively. We construct an instance of {\it Diameter-sTF} problem corresponding to the 3-SAT instance $\Psi$ using the following rules.

{\it Rule $1$} For each variable $x$, create two nodes $x, \neg x$ in $G$ and set $w(x, \neg x) = r'$.

{\it Rule $2$} For each clause $C_j$, create two nodes, $C_{j1}$ and $C_{j2}$ in $G$ and set $w(C_{j1}, C_{j2}) = r'$. 

{\it Rule $3$} Pick any $r$ such that $r < r'$. For each pair of variables ($x, y$) where $y \ne \neg x$, set $w(x, y) = r$. Similary, for each pair of clauses ($C_f, C_g$), where $w(C_f, C_g)$ is not set by rule $2$, set $w(C_f, C_g) = r$.

{\it Rule $4$} 
For each clause, $C_j = (x \vee y \vee z)$, set 

$w(C_{j1}, x) = w(C_{j1}, y) = w(C_{j1}, z) = \frac{r}{2}$ and 

$w(C_{j2}, x) = w(C_{j2}, y) = w(C_{j2}, z) = \frac{r}{2}$ and 

$w(C_{j1}, u) = w(C_{j2}, u) = r$ for each $u \in U - \{x, y, z\}$ 

{\it Rule $5$} For each $u_i, \neg u_i \in U$, associate a skill $a$ to node $u_i, \neg u_i$. And for each $C_j \in C$, associate a skill $a$ to the nodes $C_{j1}, C_{j2}$. 

\begin{claim}
\label{claim:minDiaClaim1} In $G$, $d(x, \neg x) > r$ where $x, \neg x \in U$.
\end{claim}
\begin{proof}
In $G$, for each variable $y (\ne x \ne \neg x), \ d(x, y) = d(\neg x, y) = r$ and $w(x, \neg x) = r' > r$ (rule $1, 3$). Further, both $x$ and $\neg x$ cannot appear together in any clause $C_j \in C$ (pre-processing). Therefore, in $G,\ d(C_{j1}, x) = d(C_{j2}, x) = \frac{r}{2}$ and $d(C_{j1}, \neg x) = d(C_{j2}, \neg x) = r$ (rule $3, 4$). \\
$\Rightarrow d(x, \neg x) > r$
\end{proof}
\begin{claim}
\label{claim:minDiaClaim2} Let $X$ be the subgraph of $G$ and $V(X)$ denote the nodes in $X$. Let $C_{j1}, C_{j2} \in V(X)$ where $C_j = (x \vee y \vee z)$. Then, in $X$, $d(C_{j1}, C_{j2}) = r$ iff $V(X) \cap \{x, y ,z\} \ne \phi$.
\end{claim}
\begin{proof}
Assume $V(X) \cap \{x, y, z\} = \phi$. \\
In $G$, for each clause $C_f (\ne C_{j1} \ne C_{j2}), \ d(C_{j1}, C_f) = d(C_{j2}, C_f) = r$ and $w(C_{j1}, C_{j2}) = r' > r$ (rule $2, 3$). Further, for each $u \in U - \{x, y , z\},\ d(C_{j1}, u) = d(C_{j2}, u) = r$ (rule $4$). Therefore, in $X,  d(C_{j1}, C_{j2}) > r$. However, this is a contradiction because, in $X, d(C_{j1}, C_{j2}) = r$. \\
$\Rightarrow V(X) \cap \{x, y ,z\} \ne \phi$.
\end{proof}
\begin{claim}
\label{claim:minDiaClaim3} Let  $k = N + 2M$. If $\Psi$ has a satisfying assignment then $G$ has a sub-graph $\cal X'$ with $|{\cal X'} \cap S(a)| \ge k$ and $diameter({\cal X'}) \le r$. 
\end{claim}
\begin{proof}
If $\Psi$ has a satisfying assignment, then $G$ has a subgraph $\cal X'$ such that $\cal X'$ contains $C_{j1}, C_{j2}$ for each clause $C_j \in C$, and $u (or \ \neg u) \in U$ if $u (or \  \neg u)$ is set to $1$ in the satisfying assignment for $\Psi$. Note that in the satisfying assignment for $\Psi$ either $u$ or $\neg u$ appears in the assignment. Thus, $\cal X'$ contains exactly $N$ variables and twice the number of clauses. Thus, $|{\cal X'} \cap S(a)| = N + 2M = k$ (rule $5$). \\
Since $\cal X'$ contains either a variable or it negation, for each pair of variables $(x, y) \in V(X) \cap U,\ d(x, y) = r$ (rule $3$). Further, in the satisfying assignment for $\Psi$ each clause $C_j = x \vee y \vee z$, has at least one of the variables set to $1$. So, for each pair of nodes $(p, q) \in V(X) \cap C, \ d(p, q) = r$ ({\sc Claim ~\ref{claim:minDiaClaim2} } and rule $3$) . Therefore, distance between any two nodes in $\cal X'$ is $r$ (rule $4$).\\
Thus, if $\Psi$ has a satisfying assignment then $G$ has a subgraph $\cal X'$ with $|{\cal X'} \cap S(a)| = k$ and $diameter({\cal X'}) = r$. 
\end{proof}
\begin{claim}
\label{claim:minDiaClaim4} Let  $k =  N + 2M$. If $G$ has a sub-graph $\cal X'$ with $|{\cal X'} \cap S(a)| \ge k$ and $diameter({\cal X'}) \le r$ then $\Psi$ has a satisfying assignment.
\end{claim}
\begin{proof}
If $diameter({\cal X'}) \le r$ then it contains either $u$ or $\neg u$ but not both because $d(u, \neg u) > r$ ({\sc Claim ~\ref{claim:minDiaClaim1}}). Since $k = N + 2M$, for each variable $u \in U$, $\cal X'$ contains a node corresponding to either $u$ or $\neg u$ (not both) and for each clause $C_j \in C$, $\cal X'$ contains nodes corresponding to $C_{j1}$ and $C_{j2}$ (rule $5$). Now, since $diameter({\cal X'}) \le r$, it implies that $d(C_{j1}, C_{j2}) \le r$. This implies that at least one of the nodes corresponding to $x, y, z$ in $C_j$ is included in the sub-graph $\cal X'$ ({\sc Claim ~\ref{claim:minDiaClaim2}}). Now, if each variable $u \in U \cap V({\cal X'})$ is set to $1$, then $\Psi$ has a satisfying assignment.
\end{proof}
{\sc Claims ~\ref{claim:minDiaClaim3}} and ~\ref{claim:minDiaClaim4} prove that {\it Diameter-sTF} is NP-hard. Since {\it Diameter-sTF} is the special case of {\it Diameter-mTF}, its NP-hardness proof follows.
\end{proof}

\begin{theorem}
For any graph distance function $d$ that satisfies the triangle inequality, the algorithm {\it MinDiameter} achieves an approximation factor of $2$ for the {\it Diameter-sTF} and\\
{\it Diameter-mTF} problems.
\end{theorem}
\begin{proof}
The analysis we present here is similar to the analysis of the {\it RarestFirst} algorithm presented in ~\cite{LLT}. First, consider the solution $\cal X'$ output by the {\it MinDiameter} algorithm, and let $a_{rare} \in T$ be the skill possessed by the least number of individuals in $\cal X$. Also, let $i^*$ be the individual picked from set $S(a_{rare})$ to be included in the solution $\cal X'$. Now, consider two other skills $a_1 \ne a_2 \ne a_{rare}$ and individuals $i, i' \in \cal X$ such that $i \in S(a_1), i \not \in S(a_2)$ and $i' \not \in S(a_1), i' \in S(a_2)$. If $i, i'$ are part of the team reported by the {\it MinDiameter} algorithm, it means that $d(i^*, i) \le d_k(i^*, S(a_1), k_1)$ and $d(i^*, i') \le d_k(i^*, S(a_2), k_2)$. Due to the way the algorithm operates, we can lowerbound the Cc-R cost of the optimal solution, $\cal X^*$,  as follows: 

\begin{equation}\label{DiaBounds}
d(i^*, i) \le \mbox{Cc-R}({\cal X^*}) \mbox{ and }  d(i^*, i') \le \mbox{Cc-R}({\cal X^*})
\end{equation}
Since we have assumed that the distance function $d$ satisfies the triangle inequality, \\
$d (i, i') \le d(i, i^*) + d(i^*, i')$\\
By applying the bounds given in ~\eqref{DiaBounds}, we get the proposed approximation factor. \\
$d (i, i') \le$ Cc-R($\cal X^*) +$ Cc-R(${\cal X^*}) \le 2 \cdot $Cc-R($\cal X^*$).
\end{proof}

%The algorithm {\it MinDiameter} generalizes the algorithm {\it RarestFirst} described in ~\cite{LLT}. 
Algorithm {\it MinDiameter} is as follows. For each individual, say $i_r \in S(a_{rare})$ where $a_{rare}$ is the rarest skill (the skill with the minimum size support set $S$), and for each skill $a_i \in {\cal T}$, the algorithm finds the distance to all the nodes in the support set $S(a_i)$. Then, for each support set $S(a_i)$, it chooses the $k_i$-size subset of $S(a_i)$ such that the maximum shortest path distance between $i_r$ and the nodes in this subset is minimum among all $k_i$-size subsets of $S(a_i)$. We call this distance as $k_i$-th shortest distance between $i_r$ and $S(a_i)$ and denote it as $d_k(i_r, S(a_i), k_i)$. Further, we denote the set of $k_i$ shortest paths between $i_r$ and each of the nodes belonging to the corresponding $k_i$-size subset of $S(a_i)$ as $Path_k(i_r, S(a_i), k_i)$. Thus, for each $i_r \in S(a_{rare})$ the algorithm has identified $k_i$ nodes of skill $a_i$, thereby forming a possible solution team that satisfies the constraints. Finally, the algorithm then picks one of these solutions that has minimum diameter. 
%The algorithm is presented below in detail. 
The time complexity of the algorithm {\it MinDiameter}, assuming that all pairs shortest paths are pre-computed, is $O(n^2)$.

